﻿Imports System.Collections.Generic

Public Enum eFireModelDirection
    efmdForward
    efmdBackwards
End Enum

Public Class FirePerimeterPath

    Implements IFirePerimeterPath

    Private mCrossSearchProximityThresholdDistanceMetres As Double
    Private mInsertNodeThresholdDistanceMetres As Double
    Private mMergeNodeThresholdDistanceMetres As Double

    Private mStartTime As DateTime
    Private mSimulationTime As DateTime
    Private mSpreadPotentialField As ISpreadPotentialField
    Private mFirstNode As cFirePerimeterPathNode

    ' Private Shared mStopWatch As System.Diagnostics.Stopwatch = New System.Diagnostics.Stopwatch
    ' Private Shared mElapsedMilliseconds As Long = 0

    Private mAdvancementIsBlockedForDirection As eFireModelDirection?

    Public Sub New(ByVal SimulationTime As DateTime, ByVal SpreadPotentialField As ISpreadPotentialField, ByVal InitialPath() As IMetricCoordinateTwoDimensional)

        Dim NodeLocation As IMetricCoordinateTwoDimensional
        Dim NewNode As cFirePerimeterPathNode
        Dim LatestAddedNode As cFirePerimeterPathNode

        mInsertNodeThresholdDistanceMetres = 4
        mCrossSearchProximityThresholdDistanceMetres = 3.84 ' 0.96 * mInsertNodeThresholdDistanceMetres
        mMergeNodeThresholdDistanceMetres = 1.92 ' 0.48 * mInsertNodeThresholdDistanceMetres

        mSimulationTime = SimulationTime
        mSpreadPotentialField = SpreadPotentialField
        mStartTime = SimulationTime

        InitialPath = CheckInitialPath(InitialPath)

        LatestAddedNode = Nothing
        For Each NodeLocation In InitialPath
            If Not NodeLocation Is Nothing Then
                NewNode = cFirePerimeterPathNode.CreateForLocation(NodeLocation.LocationX, NodeLocation.LocationY)
                If mFirstNode Is Nothing Then
                    mFirstNode = NewNode
                End If
                If Not LatestAddedNode Is Nothing Then
                    LatestAddedNode.AssignNextNodeInPath(NewNode)
                    NewNode.AssignPreviousNodeInPath(LatestAddedNode)
                End If
                LatestAddedNode = NewNode
            End If
        Next

        LatestAddedNode.AssignNextNodeInPath(mFirstNode)
        mFirstNode.AssignPreviousNodeInPath(LatestAddedNode)

    End Sub

    Private Function CheckInitialPath(ByVal InitialPath() As IMetricCoordinateTwoDimensional) As IMetricCoordinateTwoDimensional()

        'Does some sanity checks on the points 

        Dim PointCount As Integer
        Dim CentrePoint As IMetricCoordinateTwoDimensional
        Dim ExpansionDistanceMetres As Double

        If InitialPath.Length < 1 Then
            Throw New Exception("The initial path provided has no coordinates.")
        End If

        PointCount = InitialPath.GetUpperBound(0) + 1
        Select Case PointCount
            Case 1
                'We'll accept a single point, and auto convert it to a little diamond
                CentrePoint = InitialPath(0)
                ExpansionDistanceMetres = 3 'mInsertNodeThresholdDistanceMetres / 2
                ReDim InitialPath(3)
                InitialPath(0) = New cMetricGridCoordinate(CentrePoint.LocationX, CentrePoint.LocationY + ExpansionDistanceMetres)
                InitialPath(1) = New cMetricGridCoordinate(CentrePoint.LocationX + ExpansionDistanceMetres, CentrePoint.LocationY)
                InitialPath(2) = New cMetricGridCoordinate(CentrePoint.LocationX, CentrePoint.LocationY - ExpansionDistanceMetres)
                InitialPath(3) = New cMetricGridCoordinate(CentrePoint.LocationX - ExpansionDistanceMetres, CentrePoint.LocationY)
            Case 2
                Throw New Exception("The initial path provided is just a line with no internal area.")
            Case 3
                'It's a triangle. Can't remove a point.
                If InitialPath(0).IsSameAs(InitialPath(PointCount - 1)) Then
                    Throw New Exception("The initial path provided is just a line with no internal area.")
                End If
            Case Else
                'If the polygon is closed by the first and last points being equal, then we'll drop a point. We're doing a linked list.
                If InitialPath(0).IsSameAs(InitialPath(PointCount - 1)) Then
                    ReDim Preserve InitialPath(PointCount - 2)
                End If
        End Select

        Return InitialPath

    End Function

    Public ReadOnly Property StartTime As DateTime
        Get
            Return mStartTime
        End Get
    End Property

    Public Function GetMaximumSafeStepLengthInSeconds() As Double

        'This returns the time step which will let the node move half as far as the insert threshold distance.

        Dim CurrentNode As cFirePerimeterPathNode
        Dim NodeSpeed As Double
        Dim HighestSpeed As Double
        Dim MaximumStepSeconds As Double

        CurrentNode = mFirstNode
        Do
            NodeSpeed = CurrentNode.GetNextMoveSpeed(mSpreadPotentialField)
            HighestSpeed = Math.Max(HighestSpeed, NodeSpeed)
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

        MaximumStepSeconds = mInsertNodeThresholdDistanceMetres / 2
        MaximumStepSeconds = MaximumStepSeconds / HighestSpeed

        Return MaximumStepSeconds

    End Function

    ' Returns FALSE if path advancement is permanently blocked
    ' Could happen due to too few nodes
    ' Could also happen if the shrinking pass somehow gets pass the "inflection point" and suddenly starts growing again
    Public Function TryToAdvancePath(ByVal SimulationStepLength As TimeSpan, ByVal FireModelDirection As eFireModelDirection) As Boolean

        Dim PathNodeCountPriorToAdvance As Integer
        Dim PathNodeCountAfterAdvance As Integer

        Dim PathAreaPriorToAdvance As Double
        Dim PathAreaAfterAdvance As Double

        If mAdvancementIsBlockedForDirection = FireModelDirection Then
            Return False
        Else
            ' if not blocked for this direction we need to clear this (as the fire model direction may have recently changed)
            mAdvancementIsBlockedForDirection = Nothing
        End If

        If FireModelDirection = eFireModelDirection.efmdBackwards AndAlso Me.CountTheNodes < 4 Then
            ' we have too few nodes, advancement onwards is blocked
            mAdvancementIsBlockedForDirection = FireModelDirection
            Return False
        End If

        PathNodeCountPriorToAdvance = Me.CountTheNodes()
        PathAreaPriorToAdvance = Me.FindPathAreaMetresSquared()

        AdvancePath(SimulationStepLength, FireModelDirection)

        PathNodeCountAfterAdvance = Me.CountTheNodes()
        PathAreaAfterAdvance = Me.FindPathAreaMetresSquared()

        If PathNodeCountPriorToAdvance = PathNodeCountAfterAdvance AndAlso PathAreaPriorToAdvance = PathAreaAfterAdvance Then
            ' our advancement has stopped for some reason and is now blocked for this direction
            mAdvancementIsBlockedForDirection = FireModelDirection
            Return False
        End If

        If FireModelDirection = eFireModelDirection.efmdBackwards Then
            If PathAreaAfterAdvance > PathAreaPriorToAdvance Then
                ' our shrinking area is now growing again
                ' this could in theory happen if your MaximumSafeTimeStepSeconds rule is too big and the path nodes jump over each other and thus reverse the direction of the path
                ' if this happens we absolutely need to stop further advancements as this represent the end of our simulation
                mAdvancementIsBlockedForDirection = FireModelDirection
                Return False
                ' NOTE: We can't use path length test here, as in some cases it's perfectly OK for shrinking area to (temporarily) increase the path length
            End If
        End If
        ' NOTE: We could do similar logic for efmdForwards, but currently there is no reason to do so

        ' advance was possible
        Return True

    End Function


    Public Sub AdvancePath(ByVal SimulationStepLength As TimeSpan, ByVal FireModelDirection As eFireModelDirection)

        AdvanceAndMoveAllNodes(SimulationStepLength, FireModelDirection)

        ThinNodesTooCloseTogether()

        InsertExtraNodesAlongVertices()

        RemoveLargeInvaginations()

    End Sub


    Private Sub AdvanceAndMoveAllNodes(ByVal SimulationStepLength As TimeSpan, ByVal FireModelDirection As eFireModelDirection)

        Dim CurrentNode As cFirePerimeterPathNode

        CurrentNode = mFirstNode
        Do
            CurrentNode.AdvanceNodePosition(SimulationStepLength, mSpreadPotentialField, FireModelDirection)
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

        If FireModelDirection = eFireModelDirection.efmdForward Then
            mSimulationTime = mSimulationTime.Add(SimulationStepLength)
        ElseIf FireModelDirection = eFireModelDirection.efmdBackwards Then
            mSimulationTime = mSimulationTime.Subtract(SimulationStepLength)
        Else
            'WTF?
        End If

    End Sub

    Private Sub ThinNodesTooCloseTogether()

        Dim CurrentNode As cFirePerimeterPathNode
        Dim ActionTest As Boolean

        'Thin out the line to remove nodes which are too close to each other.

        '2012-03-08 DNH 
        'This is quite neat because it removes the current node, so keeps 'eating' along the line, even if there are multiple sequential nodes which are all too close together.
        'The interesting bit here is that by removing a node too close to the one next, the one behind it might then be not separated by so far, if we reduced the edges. 

        CurrentNode = mFirstNode
        Do
            ActionTest = CurrentNode.IsDistanceToAnotherNodeLessThan(CurrentNode.NextNodeInPath, mMergeNodeThresholdDistanceMetres)
            If ActionTest Then
                'Remove the node
                CurrentNode.PreviousNodeInPath.AssignNextNodeInPath(CurrentNode.NextNodeInPath)
                CurrentNode.NextNodeInPath.AssignPreviousNodeInPath(CurrentNode.PreviousNodeInPath)
                If CurrentNode Is mFirstNode Then
                    mFirstNode = CurrentNode.NextNodeInPath
                End If
            End If
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

    End Sub

    Private Sub InsertExtraNodesAlongVertices()

        Dim CurrentNode As cFirePerimeterPathNode
        Dim NewNodeLocation As cMetricGridCoordinate
        Dim NewNode As cFirePerimeterPathNode
        Dim WeHaveMovedOnwardsFromTheFirstNode As Boolean

        'Insert more nodes to keep the line resolution adequate
        CurrentNode = mFirstNode
        Do
            If CurrentNode.IsDistanceToNextNodeGreaterThan(mInsertNodeThresholdDistanceMetres) Then
                NewNodeLocation = CurrentNode.GetHalfWayPointToNextNeighbour
                NewNode = cFirePerimeterPathNode.CreateForLocation(NewNodeLocation.LocationX, NewNodeLocation.LocationY)
                NewNode.AssignPreviousNodeInPath(CurrentNode)
                NewNode.AssignNextNodeInPath(CurrentNode.NextNodeInPath)
                CurrentNode.NextNodeInPath.AssignPreviousNodeInPath(NewNode)
                CurrentNode.AssignNextNodeInPath(NewNode)
                ' We do not move the new node as it might be still more than mInsertNodeThresholdDistanceMetres away, we re-check this and add new nodes as many times as is needed :)
            Else
                CurrentNode = CurrentNode.NextNodeInPath
                WeHaveMovedOnwardsFromTheFirstNode = True
            End If
        Loop While Not WeHaveMovedOnwardsFromTheFirstNode OrElse Not CurrentNode Is mFirstNode

    End Sub

    Private Function CountIntermediateNodes(ByVal StartNode As cFirePerimeterPathNode, ByVal EndNode As cFirePerimeterPathNode) As Integer

        Dim CurrentNode As cFirePerimeterPathNode
        Dim Counter As Integer

        Counter = 0

        CurrentNode = StartNode
        If Not CurrentNode Is EndNode Then
            CurrentNode = CurrentNode.NextNodeInPath
            Do While Not CurrentNode Is EndNode
                Counter += 1
                CurrentNode = CurrentNode.NextNodeInPath
            Loop
        End If

        Return Counter

    End Function

    Private Function CalculateSpeedSumForPathFragment(ByVal StartNode As cFirePerimeterPathNode, ByVal EndNode As cFirePerimeterPathNode) As Double

        Dim CurrentNode As cFirePerimeterPathNode
        Dim SumOfSpeeds As Double

        SumOfSpeeds = 0

        CurrentNode = StartNode
        If Not CurrentNode Is EndNode Then
            CurrentNode = CurrentNode.NextNodeInPath
            Do While Not CurrentNode Is EndNode
                SumOfSpeeds = SumOfSpeeds + CurrentNode.GetNextMoveSpeed(mSpreadPotentialField)
                CurrentNode = CurrentNode.NextNodeInPath
            Loop
        End If

        Return SumOfSpeeds

    End Function

    Private Sub WriteNodeLocationsToDebug()

        Dim CurrentNode As cFirePerimeterPathNode
        Debug.Print("")
        CurrentNode = mFirstNode
        Do
            Debug.Print(CurrentNode.MetricLocationX & vbTab & CurrentNode.MetricLocationY & vbTab & CurrentNode.CutOperationStatus)
            CurrentNode = CurrentNode.NextNodeInPath
        Loop Until CurrentNode Is mFirstNode

    End Sub

    Private ReadOnly Property Description As String Implements IFirePerimeterPath.Description
        Get
            Return "Fire perimeter at " & Format(SimulationTime, "yyyy-MM-dd hh:mm:ss")
        End Get
    End Property

    Private ReadOnly Property SimulationTime As DateTime Implements IFirePerimeterPath.SimulationTime
        Get
            Return mSimulationTime
        End Get
    End Property

    Friend ReadOnly Property FirstNode As cFirePerimeterPathNode
        Get
            Return mFirstNode
        End Get
    End Property

    Private ReadOnly Property FirstNodeForInterface As IFirePerimeterPathNode Implements IFirePerimeterPath.FirstNode
        Get
            Return mFirstNode
        End Get
    End Property

    Friend Function CountTheNodes() As Integer Implements IFirePerimeterPath.CountTheNodes

        Dim CurrentNode As cFirePerimeterPathNode
        Dim Count As Integer

        Count = 0
        CurrentNode = mFirstNode
        Do
            Count += 1
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

        Return Count

    End Function


    Friend Function CountTheNodesAndRefreshArrayIndexesForPathSkimmer() As Integer

        Dim CurrentNode As cFirePerimeterPathNode
        Dim Count As Integer

        Count = 0
        CurrentNode = mFirstNode
        Do
            Count += 1
            CurrentNode.ArrayIndexBaseOneForPathSkimmer = Count
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

        Return Count

    End Function



    Private Function FindPathLengthMetres() As Double Implements IFirePerimeterPath.FindPathLengthMetres

        Dim CurrentNode As cFirePerimeterPathNode
        Dim Count As Double

        Count = 0
        CurrentNode = mFirstNode
        Do
            Count += CurrentNode.GetDistanceToPreviousNodeInPath()
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

        Return Count

    End Function

    Private Sub MarkAllNodesAsUntested()

        Dim CurrentNode As cFirePerimeterPathNode

        CurrentNode = mFirstNode
        Do
            CurrentNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosUntested ' must be here as we iteratively call this function all the time and each call should start in clean state
            CurrentNode = CurrentNode.NextNodeInPath
        Loop Until CurrentNode Is mFirstNode

    End Sub


    Private Sub RemoveLargeInvaginations()

        Dim NeighbourNodeFinder As INeighbourNodeFinder

        Dim WasCutPerformed As Boolean
        Dim NumberOfNodesInPath As Integer
        Dim NodesWithCloseNeighbours As List(Of cFirePerimeterPathNode)
        Dim CurrentNode As cFirePerimeterPathNode
        Dim ComparingNode As cFirePerimeterPathNode

        'WriteNodeLocationsToDebug()

        NeighbourNodeFinder = New cNeighbourNodeFinderPathSkimmer()

        Do

            'mStopWatch.Restart()

            NumberOfNodesInPath = CountTheNodesAndRefreshArrayIndexesForPathSkimmer()
            MarkAllNodesAsUntested()
            NodesWithCloseNeighbours = NeighbourNodeFinder.MakeListOfNodesWithCloseNeighbours(Me, NumberOfNodesInPath, mInsertNodeThresholdDistanceMetres, mCrossSearchProximityThresholdDistanceMetres)

            'mStopWatch.Stop()
            'mElapsedMilliseconds = mElapsedMilliseconds + mStopWatch.ElapsedMilliseconds
            'System.Console.WriteLine("Neighbour cumulative: " & mElapsedMilliseconds & " ms")

            WasCutPerformed = False
            For Each CurrentNode In NodesWithCloseNeighbours
                ComparingNode = CurrentNode.NextNodeInPath
                Do While Not ComparingNode Is mFirstNode
                    If ComparingNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosHasNearbyNeighbours Then
                        If Not CurrentNode.IsNeighbour(ComparingNode) Then
                            If CurrentNode.IsDistanceToAnotherNodeLessThan(ComparingNode, mCrossSearchProximityThresholdDistanceMetres) Then
                                WasCutPerformed = CheckForInvaginationAndCutPathIfFound(NumberOfNodesInPath, CurrentNode, ComparingNode)
                                If WasCutPerformed Then
                                    Exit For
                                End If
                            End If
                        End If
                    End If
                    ComparingNode = ComparingNode.NextNodeInPath
                Loop
            Next
        Loop While WasCutPerformed

    End Sub


    Private Function CheckForInvaginationAndCutPathIfFound(ByVal NumberOfNodesInPath As Integer, ByVal FirstNode As cFirePerimeterPathNode, ByVal SecondNode As cFirePerimeterPathNode) As Boolean

        'Both nodes passed in are spatially close, but not path-neighbours of each other
        'The FirstNode will always arise before the SecondNode in the path

        Dim CountOfIntermediateNodes As Integer
        Dim NextNode As cFirePerimeterPathNode
        Dim Angle As Double
        Dim TestAngle As Double
        Dim DidWeCut As Boolean
        TestAngle = 180

        CountOfIntermediateNodes = CountIntermediateNodes(FirstNode, SecondNode)

        DidWeCut = False

        ' due to X axis ordering the count of cut of points could return the big main path instead of the path to be potentially cut off
        ' identify if this happens and switch current/compare nodes around in the following logic, so we focus on shorter path
        If CountOfIntermediateNodes > NumberOfNodesInPath / 2 Then

            ' 2012-10-04 Vesa Kivistö
            ' Sometimes it is possible that large segment of the full path is "stuck" along non-burning area
            ' This is more likely if we are in reverse time mode
            ' If the stuck path segment is larger, when the path would be cut so that the stuck path would remain and the real active path would be discarded
            ' We do not want this, so we need to check the "sum velocity" for both prospective path segments and base the cutting decision on that

            ' TO BE DONE
            'Dim SumOfSpeedFirstToSecondPathFragment As Double
            'Dim SumOfSpeedSecondToFirstPathFragment As Double
            'SumOfSpeedFirstToSecondPathFragment = CalculateSpeedSumForPathFragment(FirstNode, SecondNode)
            'SumOfSpeedSecondToFirstPathFragment = CalculateSpeedSumForPathFragment(SecondNode, FirstNode)

            'If SumOfSpeedSecondToFirstPathFragment > SumOfSpeedFirstToSecondPathFragment Then
            '    ' reverse
            '    Dim TempNode As cFirePerimeterPathNode
            '    TempNode = FirstNode
            '    FirstNode = SecondNode
            '    SecondNode = TempNode
            'End If

            ' OLD WAY
            Dim TempNode As cFirePerimeterPathNode
            TempNode = FirstNode
            FirstNode = SecondNode
            SecondNode = TempNode


        End If

        ' Let's draw a line from BeginNode to BeginNode.Next
        ' If EndNode is on the "left side" of the line, we have detected an invagination (which should be cut)      => angle from Next to End is < 180
        ' If EndNode is on the "right side" of the line, we have detected an extrusion (which should NOT be cut)    => angle from Next to End is <180
        NextNode = FirstNode.NextNodeInPath
        Angle = FirstNode.GetAngleFormedWithTwoOtherNodesDegrees(NextNode, SecondNode)
        If Angle < TestAngle Then
            PerformCutting(FirstNode, SecondNode)
            DidWeCut = True
            'WriteNodeLocationsToDebug()
        Else
            ' Standard extrusion do nothing
        End If

        Return DidWeCut

    End Function

    Private Sub PerformCutting(ByVal CutStartNode As cFirePerimeterPathNode, ByVal CutEndNode As cFirePerimeterPathNode)

        Dim CurrentNode As cFirePerimeterPathNode

        'Tie the path cut-off points together.
        CutStartNode.AssignNextNodeInPath(CutEndNode)
        CutEndNode.AssignPreviousNodeInPath(CutStartNode)

        CutEndNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosProcessed
        CutStartNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosProcessed

        ' 2012-10-03 Vesa Kivistö
        ' Lets just always reallocate mFirstNode, can be done and is even faster
        mFirstNode = CutStartNode

        ' 2012-10-03 Vesa Kivistö: Agree that this likely could be removed
        ' Probably redundant, but for clarity, mark the removed nodes as removed
        CurrentNode = CutStartNode.NextNodeInPath
        Do While Not CurrentNode Is CutEndNode
            CurrentNode.CutOperationStatus = cCutOperationTarget.eCutOperationStatus.ecosRemoved
            CurrentNode = CurrentNode.NextNodeInPath
        Loop

    End Sub

    Private Function FindPathAreaMetresSquared() As Double Implements IFirePerimeterPath.FindPathAreaMetresSquared


        ' See http://www.mathopenref.com/coordpolygonarea2.html
        ' Primary path is already clockwise
        ' Secondary path area must be reversed

        Dim AreaAccumulator As Double
        Dim FirstNode As cFirePerimeterPathNode
        Dim ComparingNode As cFirePerimeterPathNode
        Dim PartIncrementX As Double
        Dim PartIncrementY As Double
        Dim AreaIncrement As Double

        AreaAccumulator = 0

        FirstNode = mFirstNode
        ComparingNode = mFirstNode.PreviousNodeInPath
        Do
            PartIncrementX = ComparingNode.MetricLocationX + FirstNode.MetricLocationX
            PartIncrementY = ComparingNode.MetricLocationY - FirstNode.MetricLocationY
            AreaIncrement = PartIncrementX * PartIncrementY
            AreaAccumulator += AreaIncrement
            ComparingNode = FirstNode
            FirstNode = FirstNode.NextNodeInPath
        Loop While Not FirstNode Is mFirstNode

        AreaAccumulator = Math.Abs(AreaAccumulator)
        AreaAccumulator = AreaAccumulator / 2

        Return AreaAccumulator

    End Function

    Private Sub PrintNodesToDebug()

        Dim CurrentNode As cFirePerimeterPathNode

        Debug.Print("")
        CurrentNode = mFirstNode
        Do
            Debug.Print(CLng(CurrentNode.MetricLocationX) & "  " & CLng(CurrentNode.MetricLocationY))
            CurrentNode = CurrentNode.NextNodeInPath
        Loop While Not CurrentNode Is mFirstNode

    End Sub

End Class